package com.test.daily.leetcode.y2022.m07.day0712.v03;

import java.util.Stack;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/7/12 下午 06:47
 * @version: 1.0
 */
public class Solution {

    public static class Node{
        int value;
        Node last;
        Node next;
        public Node(int value){
            this.value = value;
        }
    }

    public static class HeadTail{
        Node h;
        Node t;
        public HeadTail(Node head, Node tail){
            this.h = head;
            this.t = tail;
        }
    }

    public static class Info{
        Node lh;
        Node lt;
        int ls;
        Node eh;
        Node et;
        Node rh;
        Node rt;
        int rs;
        public Info(Node lh, Node lt, int ls, Node eh, Node et, Node rh, Node rt, int rs){
            this.lh = lh;
            this.lt = lt;
            this.ls = ls;
            this.eh = eh;
            this.et = et;
            this.rt = rt;
            this.rh = rh;
            this.rs = rs;
        }
    }
    public static void quickSort(Node h){
        Node root = h;
        int N = 0;
        while(root.next == null){
            N++;
            root = root.next;
        }
        Node R = root;
        process(h, R, N);
    }
    public static Info partition(Node L, Node pivot){
            Node lh = null;
            Node lt = null;
            int ls = 0;
            Node eh = pivot;
            Node et = pivot;
            Node rh = null;
            Node rt = null;
            int rs = 0;
            while(L != null){
                Node tmp = L.next;
                if(L.value < pivot.value){
                    ls++;
                    if(lh == null){
                        lh = L;
                        lt = L;
                    } else {
                        lt.next = L;
                        L.last = lt;
                        lt = L;
                    }
                } else if(L.value > pivot.value){
                    rs++;
                    if(rt == null){
                        rh = L;
                        rt = L;
                    } else {
                        rt.next = L;
                        L.last = rt;
                        rt = L;
                    }
                }else{
                    et.next = L;
                    L.last = et;
                    et = L;
                }
                L = tmp;
            }
            return new Info(lh,lt,ls,eh,et,rh,rt,rs);
    }
    public static HeadTail process(Node L, Node R, int N){
        int randomIndex = (int)Math.random() *N;
        Node randomNode = L;
        while(randomIndex-- >= 0){
            randomNode = L.next;
        }
        if(randomNode == L || randomNode == R){
            if(randomNode == L){
                randomNode = L;
                L = L.next;
                L.last = null;
            } else {
                randomNode = R;
                randomNode.last.next = null;
            }
        } else {
            randomNode.last.next = randomNode.next;
            randomNode.next.last = randomNode.last;
        }
        randomNode.last = null;
        randomNode.next = null;
        Info info = partition(L, randomNode);
        HeadTail lht = process(info.lh, info.lt, info.ls);
        HeadTail rht = process(info.rh, info.rt, info.rs);
        if(lht.t != null){
            lht.t.next = info.eh;
            info.eh.last = lht.t;
        }
        if(rht.h != null){
            info.et.next = rht.h;
            rht.h.last = info.et;
        }
        Node h = lht.h == null? lht.h : info.eh;
        Node t = rht.t == null? rht.t: info.et;
        return new HeadTail(h, t);
    }


}
